package leetcode;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-01-19 23:38
 **/
public class LeetCode279 {

    public int numSquares(int n) {
        //是完全平方数,直接返回1
        if (isPerfectSquare(n)) {
            return 1;
        }

        //满足4平方和定理,返回4
        if (checkAnswer4(n)) {
            return 4;
        }

        //判断由2个完全平方数构成的情况
        for (int i = 1; i * i <= n; i++) {
            int j = n - i * i;
            if (isPerfectSquare(j)) {
                return 2;
            }
        }

        //排除法,非1,2,4,则3
        return 3;
    }

    // 判断是否为完全平方数
    public boolean isPerfectSquare(int x) {
        int y = (int) Math.sqrt(x);
        return y * y == x;
    }

    // 判断是否能表示为 4^k*(8m+7),能表示,说明可以被四个完全平方数构成,否则只可能由1或2或3个完全平方数构成
    public boolean checkAnswer4(int x) {
        while (x % 4 == 0) {
            x /= 4;
        }
        return x % 8 == 7;
    }

    //动态规划
    /*public int numSquares(int n) {
        //dp[i]: 构成i的完全平方数的最少数量
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            dp[i] = i;
            for (int j = 1; j * j <= i; ++j) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }

        return dp[n];
    }*/


}
